package LearnDataStructure.c_树结构.例题;

import LearnDataStructure.c_树结构.BSTNode;
import LearnDataStructure.c_树结构.有序树.二叉树.b_MyBinaryTreebyLinked;
/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-12 21:23
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.例题
 */
/*
因为中序遍历是有规律的
中序遍历BST是递增的
要运用递增这个关键规则！
 */
public class f_判断二叉树是否为二叉搜索树 {
    public static void main(String[] args) {
        f_判断二叉树是否为二叉搜索树 test = new f_判断二叉树是否为二叉搜索树();
        b_MyBinaryTreebyLinked<Integer, Integer> binaryTree = new b_MyBinaryTreebyLinked<>();
        binaryTree.insert(6,6);
        binaryTree.insert(7,7);
        binaryTree.insert(4,4);
        binaryTree.insert(5,5);
        binaryTree.insert(8,8);
        binaryTree.insert(2,2);

        System.out.println(test.checkBST(binaryTree.getRoot()));
    }

    private Integer perValue = Integer.MIN_VALUE;

    public boolean checkBST(BSTNode<Integer, Integer> node) {
        if (node == null) {
            return true;
        }
        boolean leftCheck = checkBST(node.left);
        if (!leftCheck) {//leftCheck == false
            return false;
        }
        if (node.value <= perValue) {
            return false;
        }
        perValue = node.value;//第一次赋值，是整棵树的最左节点value赋给perValue
        //走到这里，代表node的左支完全符合BST,那么只需要判断右支是否符合就行了
        return checkBST(node.right);
    }
}
